The present invention relates to data processing systems, and more particularly to multiprocessor systems.
There are known computer architectures in which two or more data processors are linked to cooperatively utilize a common main memory. In such multi-processor systems, there are often operating conditions wherein a first processor might utilize information stored at a location in the main memory, modify that information internally and then write the modified information back to the original location in the main memory. While this process is going on, a second processor may also require updated information associated with the same location in the main memory. In order to accommodate such situations, multiprocessor systems must incorporate a protocol to permit each processor to know whether the information stored in the various main memories is stale or reflects current information.
In one particular prior art form, exemplified by the 850 System, manufactured by Prime Computer, Framingham, Mass., two data processors (DP-1 and DP-2) are coupled by way of a common memory bus (MB) to a main memory (MM). Each of the processors DP-1 and DP-2 includes a central processing unit (CPU-1 and CPU-2, respectively) and a local cache memory (LC-1 and LC-2, respectively). In this configuration, for example, each local cache memory may store an image portion of a program-to-be-executed which is stored in full in the main memory. The image program is stored in a format including a succession of words, each word having a tag portion, T, (representative of a page number, or high order location-defining bits in main memory) and associated data portions, D, (representative of the contents of the corresponding location in the main memory). In this format, the word number of each word in the stored succession in the cache memory is representative of the low-order location-defining bits in main memory. That is each local cache memory entry fully specifies a location in main memory, and the contents of that location. In operation, the local cache memories make this information available to their associated central processor, on request, on a high speed basis.
In this configuration, during operation, one data processor (DP-1) might modify the data associated with a main memory location in its local cache memory (LC-1). Since in the System 850, the local cache memories are "write-through" caches, the corresponding change is also written in the appropriate location in main memory. However, the other processor (DP-2) already may have stored the original contents of that location in main memory in its local cache memory (LC-2). Thus, unless the second data processor DP-2 is advised, it may request the information from its cache memory (LC-2) which is "stale"; that is, the requested information does not correspond to the "modified" information currently stored at the location in main memory.
In order to prevent the use of such stale information, systems in the prior art, such as the System 850, include a system for detecting changes in information in the local cache memories of each processor coupled to the main memory, and for identifying to the respective data processors the particular entries in their local cache memory which are stale (or invalid); that is, those entries which correspond to locations in main memory whose contents have been modified by another data processor. With such information, the CPU's of the respective processors, upon requesting an identified invalid cache entry, declare a "cache miss" condition and go directly to main memory to read the requested information.
In the prior art systems, there is, in effect, a table associated with each local cache memory, which table includes a succession of entries (or words) initially corresponding to the tag portions of each entry (or word) in the local cache memory. In addition, there is an LIFO (or FIFO) memory associated with each local cache memory. Each data processor is adapted to transmit a cache change signal (representative of the location in main memory of the change) on the memory bus each time a cache change is made in the local cache memory at that respective data processor. On "write through" cache systems like the Prime System 850, the cache change signal may be the normal write signal. There is a controller associated with each data processor which identifies each cache change signal on the memory bus, and upon such identification, stores a signal representative of the local cache memory location in the LIFO (or FIFO) register associated with the data processor. Thus, a cumulative record of cache changes is made in the respective LIFO (or FIFO) registers.
In operation, each data processor is adapted so that periodically, or in response to the execution of selected instructions, its associated LIFO (or FIFO) register is interrogated (on a LIFO or FIFO basis) so that the contents may be used by the data processor's CPU to identify which of the entries in its local cache memory is stale (or invalid).
Thus, with this prior art configuration, each data processor is apprised of changes in the data in the respective locations of the main memory. This may occur both in systems which have "write-through" local caches, or where the caches may just accumulate data changes which might be subsequently written to main memory in a batch.
While this prior art approach does permit the necessary intercommunication between processors, the use of a separate "tag table" memory (originally duplicating the local cache memory) and a necessarily (as a practical matter) large LIFO (or FIFO) memory to store all of the cache changes which may occur, requires a substantial amount of hardware, and associated circuit complexity. Further, due to the requirement to process each entry in the LIFO (or FIFO) registers separately (some of with may correspond to multiple changes in the same main memory location) results in unnecessary, and time consuming processing.
Accordingly, it is an object of the present invention to provide an improved multiprocessor system.
It is another object to provide a multiprocessor system which communicates the occurrence of local cache changes between processors on a hardware efficient basis.
Another object is to provide a multiprocessor system which permits multiple processors to timewise effectively identify changes in cache memory throughout the system.